#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+99;
int n,m,q,a[N];
namespace brute{
    pair<int,int> que[N]; int hh,tt;
    void solve(int l,int r){
        ll ans=0,sum=0; hh=1; tt=0;
        for(int i=l;i<=r;i++){
            while(hh<=tt&&que[hh].first<=i-m) sum-=que[hh].second,hh++;
            if(sum<a[i]){
                ans+=a[i]-sum;
                que[++tt]=make_pair(i,a[i]-sum);
                sum=a[i];
            }
            else{
                while(sum>a[i]){
                    if(sum-que[hh].second>=a[i]) sum-=que[hh].second,hh++;
                    else que[hh].second-=sum-a[i],sum=a[i];
                }
            }
        }
        cout<<ans<<'\n';
        return;
    }
    void solve(){
        int l,r;
        while(q--){
            cin>>l>>r;
            solve(l,r);
        }
        return;
    }
}
int main(){
    freopen("clear.in","r",stdin);
    freopen("clear.out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n<=5000&&m<=5000) brute::solve();
    return 0;
}